#include"order.h"
//传入数组以及最大数量
//插入排序
void InsertSort(int array[], int n)
{
	int s, t, q;
	s = 1;//从第二个数据开始插入，因为数组从0开始数
	while (s < n)
	{
		t = array[s];//用t来暂存数据
		for (q = s - 1; q >= 0 && t < array[q]; q--)
			//每次q--是为了向前依次比较，
			//同时优化条件，如果取出的数据比暂存的数据大（if条件），
			//那就不需要再去依次比较，直接插到最前面就可以
			array[q + 1] = array[q];//挪动数组，以便插入数据
		array[q + 1] = t;//取出的数据大的，直接执行此步操作，找到正确位置
		s++;//保证每次向前取一个数据
	}
}
//希尔排序
void ShellSort(int array[], int n, int dd[], int t)
{
	int s, x, k, h;
	int y;
	for (s = 0; s < t; s++)//每一次循环使用一个增量，最后一个增量是1
	{
		h = dd[s];//增量序列的赋值，t记录的是有多少个增量
		for (x = h; x < n; x++)//对增量序列排序
		{
			y = array[x];//使用y来暂存数据
			for (k = x - h; k >= 0 && y < array[k]; k -= h)
				//优化了循环条件，相当于同时加上了一个if条件
				//来判断所取出的数据是否大于要比较的数，如果是才进行循环
				array[k + h] = array[k];//对增量为h的数比较后进行交换，小的换到数组前面
				//（初始的k+h就是x，但由于每次k都需要变化一个增量，所以写k-h比较方便）
			array[k + h] = y;//对于一个小于的数，直接交换就可以，在增量形成的一个数列里实现排序
		}
	}
}
//冒泡排序
void BubbleSort(int array[], int n)
{
	int s, m, t;
	m = 0;
	while (m < n - 1)//当 m == n - 1 的时候结束循环
	{
		for (s = n - 1; s >= m + 1; s--)//从后向前排序
			if (array[s] < array[s - 1])
			{
				t = array[s];//t用来暂存数据，每次取出较小的数据
				array[s] = array[s - 1];//每次都把数据大的赋值给靠后位置的数组元素
				array[s - 1] = t;//把暂存的数据赋值给之前的大的数，保证两个数据实现了交换
			}
		m++;//每一次循环都会找出最小的数
	}
}
//选择排序
void SelectSort(int array[], int n)
{
	int k, q, s, t;
	for (s = 0; s < n; s++)//每次都向前完成一次
	{
		k = s;//k用来记录变化的位置
		for (q = s + 1; q < n; q++)//每次都在没有排序的数组里进行循环
			if (array[k] > array[q])
				k = q;//挑没排序的数组里数据最小的
		t = array[s];//用t来暂时存储数据（为了与后面的小数组交换）
		array[s] = array[k];//把数据最小的赋值
		array[k] = t;//把暂存的数据赋值给原来值小的，实现交换
	}
}
//快速排序
void QuickSort(int array[], int min, int max)
{
	int head, tail;//head和tail用来记录初始数组的第一个元素和最后一个元素位置
	int t;
	if (min < max)
	{
		head = min;//head来存下标
		tail = max;//tail来存下标
		t = array[head];//暂存数据
		while (head != tail)
		{
			while (head < tail && array[tail] >= t)//如果尾部比t大，一直到尾部比t小，找到那个下标
				tail--;//尾部左移
			if (head < tail)
				array[head++] = array[tail];//进行交换的同时，因为已经做了比较，所以头部下标右移
			while (head < tail && array[head] <= t)//如果头部比暂存的数据t小，一直到比尾部大的停
				head++;//头部右移
			if (head < tail)
				array[tail--] = array[head];//进行交换的同时，尾部下标左移
		}//头和尾相遇了就跳出循环，这是一次排序
		array[head] = t;//把暂存的数据给这个确定的位置
		QuickSort(array, min, head - 1);//左边都是小于等于上面的确定位置，再递归进行快排
		QuickSort(array, head + 1, max);//右边都是大于等于上面的确定位置，递归进行快排
	}
}
//堆排序以及其全部函数
void PercDown(int array[], int s, int n)//大顶堆
{
	int q;
	int t;
	t = array[s];//暂存父节点数据
	while ((q = 2 * s + 1) < n)//根节点建堆
	{
		if (q < n - 1 && array[q] < array[q + 1])//若存在右子树且右子树关键字大，则沿着右分支筛选
			q++;
		if (t < array[q])//只要子节点大于父节点就向上交换，否则跳出循环
		{
			array[(q - 1) / 2] = array[q];//将孩子的关键字放入根节点
			s = q;//将根节点位置变为孩子下标
		}
		else
			break;
	}
	array[(q - 1) / 2] = t;//
}
void HeapSort(int array[], int n)
{
	int s;
	int t;
	s = (n - 1)/ 2;//n/2向下取整
	while (s >= 0)
	{
		PercDown(array, s, n);//s是父结点下标，n是数据数
		s--;
	}//建堆
	s = n - 1;//s是循环条件，也是最后一个元素的下标
	while (s > 0)
	{
		t = array[0];
		array[0] = array[s];
		array[s] = t;//交换堆顶和数组最后的元素数据
		PercDown(array, 0, s);//堆顶元素放到数组最后，剩下的元素再次建堆
		s--;
	}
}
//归并的排序的全部函数
int Min(int x, int y) 
{
	return x < y ? x : y;//三目运算，如果x<y,那么取x，否则取y
}
void MergeSort(int arr[], int n) 
{
	int* a = arr;
	int* b = (int*)malloc(n * sizeof(int));
	int seg, start;
	for (seg = 1; seg < n; seg += seg)//seg实现对数组进行分割，由1到MAX
	{
		for (start = 0; start < n; start += 2 * seg)//跨越已经比较的数据
		{
			int low = start, mid = Min(start + seg, n), high = Min(start + 2 * seg, n);
			//使用MIN函数来保证数组不越界，并且low，mid，high来分割数组
			int k = low;
			int start1 = low, end1 = mid;
			int start2 = mid, end2 = high;//  start1 1 3 5 7 end1|strat2 2 4 6 8 end2
			//合并有序升序数组
			while (start1 < end1 && start2 < end2)//任一数组没有到达边界则进行遍历
			{
				if (a[start1] < a[start2])
					b[k++] = a[start1++];//存储a的值并移动k
				else
					b[k++] = a[start2++];//存储a的值并移动k
			}//主要是实现初步的排序
			while (start1 < end1) //如果a数组有剩余，将a数组剩余部分拼接到合并结果的后面
				b[k++] = a[start1++];
			while (start2 < end2) //如果b数组有剩余，将b数组剩余部分拼接到合并结果的后面
				b[k++] = a[start2++];
		}
		int* temp = a;
		a = b;
		b = temp;
	}
	if (a != arr) 
	{
		int i;
		for (i = 0; i < n; i++)
			b[i] = a[i];
		b = a;
	}
	free(b);//释放开辟的内存空间
}
//基数排序的全部函数
//找到整个序列中的最大值
int getMax(int array[])//用来确定位数（如果每个数位数相同，则不需要此函数）
{
	int i, max = array[0];
	for (i = 1; i < MAX; i++)
		if (array[i] > max)
			max = array[i];
	return max;
}
//计数排序
void RadixSort(int array[], int place) 
{
	int i, output[MAX];//初始化一个数组,记录各个元素
	int count[10] = { 0 };
	for (i = 0; i < MAX; i++)
		count[(array[i] / place) % 10]++;
	//累加 count 数组中的出现次数
	for (i = 1; i < 10; i++)  //核心是找到count数组
		count[i] += count[i - 1];//新count数组表示位置信息即所在位置范围
	//根据 count 数组中的信息，找到各个元素排序后所在位置，存储在 output 数组中
	for (i = MAX - 1; i >= 0; i--) 
	{
		output[count[(array[i] / place) % 10] - 1] = array[i];//count[i]可不是i，而是i的位置范围
		//count[(array[i] / place) % 10] - 1 --> 
		//排序后的正确位置，同一数据的最后一个元素必在最后的位置 1 4 5 1 4 5 1 --> 1 1 1 4 4 5 5
		//由于每次倒着取，就能保证在后面的数据还在后面，即稳定性
		count[(array[i] / place) % 10]--;//已经找出一个数，则此数的范围缩减1
	}
	for (i = 0; i < MAX; i++)
		array[i] = output[i];//把第一次排序后的数组重新赋值给array[i]
}
//基数排序算法（基于计数）
void radixSort(int array[])
{
	int place, max = getMax(array);//找到序列中的最大值
	for (place = 1; max / place > 0; place *= 10)
		RadixSort(array, place);//每次都使用上次已经排序的数组
}







